/*
 * @Author: 0x9DEFA478
 * @Date: 2025-08-28 20:31:10
 * @LastEditTime: 2025-09-20 23:38:03
 * @LastEditors: 0x9DEFA478
 * @Description: 
 * 
 */
#ifndef hContainer_H_Stack_HPP_
#define hContainer_H_Stack_HPP_
#include "H_Type.hpp"
#include "./Memory/H_Allocator.hpp"


namespace H{

#if __cplusplus >= 202000L
  template<typename ItemType,Concept::allocator Allocator=AllocatorDefault>
#else
  template<typename ItemType,typename Allocator=AllocatorDefault>
#endif
  class Stack{
    static_assert(std::is_destructible_v<ItemType>);
#if __cplusplus < 202000L
    static_assert(is_allocator_v<Allocator>);
#endif

    private:
      struct ObjectSegment{
        ObjectSegment* Last;

        static constexpr usize HeaderSize(){return IncreaseAlignTo(sizeof(ObjectSegment),alignof(ItemType));}

        static ItemType* ToItem(ObjectSegment* objectSegment,usize Index)noexcept{
          auto p=&reinterpret_cast<byte*>(objectSegment)[HeaderSize()];
          return reinterpret_cast<ItemType*>(&p[sizeof(ItemType)*Index]);
        }
        
        static ObjectSegment* Alloc(usize ItemCount){
          return static_cast<ObjectSegment*>(Allocator::Alloc(HeaderSize()+sizeof(ItemType)*ItemCount));
        }

        static void Free(ObjectSegment* objectSegment)noexcept{
          Allocator::Free(static_cast<void*>(objectSegment));
        }
      };

    private:

      ItemType* List_At(usize Index)const{
        auto segment=current_segment;
        auto countPerSegment=this->countPerSegment;

        if(Index<=currentIndex){
          return ObjectSegment::ToItem(current_segment,currentIndex-Index);
        }

        segment=segment->Last;
        Index-=currentIndex;
        while(Index>countPerSegment){
          segment=segment->Last;
          Index-=countPerSegment;
        }
        return ObjectSegment::ToItem(segment,countPerSegment-Index);
      }

      void Dispose()noexcept{
        auto segment=current_segment;
        auto count=currentIndex+1;

        while(segment!=nullptr){
          while(count>0){
            count--;
            ObjectSegment::ToItem(segment,count)->~ItemType();
          }
          auto fp=segment;
          segment=fp->Last;
          ObjectSegment::Free(fp);
          count=countPerSegment;//底部的缓冲区是满的
        }
      }

      ObjectSegment* Copy()const{
        ObjectSegment* r=nullptr;
        ObjectSegment* dst_segment=nullptr;
        ObjectSegment* segment=current_segment;
        auto length=currentIndex+1;

        while(segment!=nullptr){
          auto new_segment=ObjectSegment::Alloc(countPerSegment);
          if(dst_segment==nullptr){
            r=new_segment;
          }else{
            dst_segment->last=new_segment;
          }
          dst_segment=new_segment;
          
          for(std::size_t i=0;i<length;i++){
            new(ObjectSegment::ToItem(dst_segment,i))ItemType(*ObjectSegment::ToItem(segment,i));
          }

          segment=segment->last;
          length=countPerSegment;
        }
        if(dst_segment!=nullptr){
          dst_segment->last=nullptr;
        }
        return r;
      }

    public:
      template<typename T=ItemType>
      class Iterator{
        
        private:
          explicit Iterator(ObjectSegment* segment,usize index,usize countPerSegment)noexcept:segment(segment),index(index),countPerSegment(countPerSegment){}

        public:
          ~Iterator()noexcept=default;

          Iterator(const Iterator&)noexcept=default;
          Iterator(Iterator&&)noexcept=default;

          T* GetPointer()const noexcept{return ObjectSegment::ToItem(segment,index);}
          T* operator->()const noexcept{return ObjectSegment::ToItem(segment,index);}

          T& operator*()const noexcept{return *ObjectSegment::ToItem(segment,index);}

          Iterator operator++(int)noexcept{Iterator r(segment,index,countPerSegment);++(*this);return r;}
          Iterator& operator++()noexcept{
            if(index>0){
              index--;
            }else{
              index=countPerSegment-1;
              segment=segment->Last;
            }
            return *this;
          }

          bool operator==(const Iterator& iterator)const noexcept{return (segment==iterator.segment)&&((segment==nullptr)||(index==iterator.index));}
          bool operator!=(const Iterator& iterator)const noexcept{return !(*this==iterator);}

        private:
          ObjectSegment* segment;
          usize index;
          usize countPerSegment;

          friend class Stack;
      };

    public:
      explicit Stack(usize countPerSegment=32)
        :current_segment(nullptr)
        ,currentIndex(0)
        ,length(0)
        ,countPerSegment(countPerSegment)
      {}

      ~Stack()noexcept{
        Dispose();
      }

      Stack(const Stack& stack)
        :current_segment(stack.Copy())
        ,currentIndex(stack.currentIndex)
        ,length(stack.length)
        ,countPerSegment(stack.countPerSegment)
      {}

      Stack(Stack&& stack)noexcept
        :current_segment(stack.current_segment)
        ,currentIndex(stack.currentIndex)
        ,length(stack.length)
        ,countPerSegment(stack.countPerSegment)
      {
        stack.current_segment=nullptr;
      }

      Stack& operator=(Stack&& stack)noexcept{
        if(this==&stack){
          return *this;
        }
        Dispose();
        current_segment=stack.current_segment;
        currentIndex=stack.currentIndex;
        length=stack.length;
        countPerSegment=stack.countPerSegment;
        stack.current_segment=nullptr;
        return *this;
      }

      Stack& operator=(const Stack& stack){
        if(this==&stack){
          return *this;
        }
        Dispose();
        current_segment=stack.Copy();
        currentIndex=stack.currentIndex;
        length=stack.length;
        countPerSegment=stack.countPerSegment;
        return *this;
      }

      template<typename... T_Arg>
      ItemType& Push(T_Arg&&... Args){
        auto segment=current_segment;
        auto countPerSegment=this->countPerSegment;
        usize Index;

        if(segment==nullptr){
          segment=ObjectSegment::Alloc(countPerSegment);
          segment->Last=nullptr;
          Index=0;
          current_segment=segment;
          currentIndex=Index;
        }else{
          Index=currentIndex+1;
          if(Index>=countPerSegment){
            Index=0;
            auto p=ObjectSegment::Alloc(countPerSegment);
            p->Last=segment;
            segment=p;
            current_segment=p;
          }
          currentIndex=Index;
        }

        length++;

        return *new(ObjectSegment::ToItem(segment,Index))ItemType(std::forward<T_Arg>(Args)...);
      }

      template<typename T>
      ItemType& Push(std::initializer_list<T>&& initializer_list){return Push(initializer_list);}

      /**
       * @brief 弹出栈顶元素
       *        用户需保证不Pop空的栈, 否则会引发未定义行为
       *        可用Empty判断栈是否为空
       * @return 无
       */
      void Pop()noexcept{
        auto segment=current_segment;
        auto Index=currentIndex;

        length--;

        ObjectSegment::ToItem(segment,Index)->~ItemType();
        if(Index>0){
          currentIndex=Index-1;
          return;
        }

        current_segment=segment->Last;
        ObjectSegment::Free(segment);
        currentIndex=countPerSegment-1;
      }

      const bool Empty()const noexcept{return current_segment==nullptr;}

      const ItemType& Top()const noexcept{
        return *ObjectSegment::ToItem(current_segment,currentIndex);
      }

      ItemType& Top()noexcept{
        return *ObjectSegment::ToItem(current_segment,currentIndex);
      }

      /**
       * @brief 倒序索引, Top()为0, 下一个为1...
       *        
       * @param Index 索引
       * @return 元素的引用
       */
      const ItemType& operator[](usize Index)const noexcept{return *List_At(Index);}

      /**
       * @brief 倒序索引, Top()为0, 下一个为1...
       * @param Index 索引
       * @return 元素的引用
       */
      ItemType& operator[](usize Index)noexcept{return *List_At(Index);}

      usize Length()const noexcept{return length;}

      Iterator<const ItemType> begin()const noexcept{return Iterator<const ItemType>(current_segment,currentIndex,countPerSegment);}
      Iterator<const ItemType> end()const noexcept{return Iterator<const ItemType>(nullptr,0,countPerSegment);}
      Iterator<ItemType> begin()noexcept{return Iterator(current_segment,currentIndex,countPerSegment);}
      Iterator<ItemType> end()noexcept{return Iterator(nullptr,0,countPerSegment);}

    private:
      ObjectSegment* current_segment;
      usize currentIndex;
      usize length;
      usize countPerSegment;
  };

}


#endif //hContainer_H_Stack_HPP_
